#pragma once

#include "../alloc.h"

namespace sfc::collections::hash {

using C = u8;
using V = u8 __attribute__((__vector_size__(16)));

struct Ctrl {
  static constexpr auto LEN = 16u;
  static constexpr auto NIL = 0xFF;

  struct Iter {
    i32 _0;

    [[sfc_inline]] operator bool() const {
      return _0 != 0;
    }

    [[sfc_inline]] auto next() -> i32 {
      const auto x = __builtin_ctz(_0);
      _0 = _0 & (_0 - 1);
      return x;
    }
  };

  V _0;

  static auto load(const u8* p) -> Ctrl {
    auto res = Ctrl{};
    __builtin_memcpy_inline(&res, p, sizeof(res));
    return res;
  }

  [[sfc_inline]] auto match(u8 x) const -> Iter {
    return {__builtin_ia32_pmovmskb128(_0 == V{x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x})};
  }
};

template <class T>
struct Table {
  using Buf = vec::RawVec<T>;

  Buf _buf;
  usize _msk;
  usize _len;

  Table() noexcept : _buf{}, _msk{0}, _len{0} {}

  Table(Buf buf, usize msk, usize len) noexcept : _buf{mem::move(buf)}, _msk{msk}, _len{len} {}

  Table(Table&& other) noexcept : _buf{mem::move(other._buf)}, _msk{other._msk}, _len{other._len} {}

  ~Table() {
    this->clear();
  }

  auto with_capacity(usize capacity) -> Table {
    if (capacity == 0) {
      return Table{};
    }
    auto cap = 1;
    while (cap < capacity) {
      cap *= 2;
    }
    return {Buf::with_capacity(cap), cap - 1, 0};
  }

  [[sfc_inline]] auto len() const -> usize {
    return _len;
  }

  [[sfc_inline]] auto capacity() const -> usize {
    return _msk + 1;
  }

  [[sfc_inline]] auto operator[](usize idx) -> T& {
    return reinterpret_cast<T*>(_buf._ptr + _msk + 1 + Ctrl::LEN)[idx];
  }

  auto search(usize hash, const auto& key) const -> T* {
    const auto h1 = hash & _msk;
    const auto h2 = u8(hash >> 57);

    for (auto h3 = h1;; hi = (hi + Ctrl::LEN) & _msk) {
      const auto hm = Ctrl::load(_buf._ptr + hi);
      for(auto hi: hm.match(h2)) {

      }
      for (auto itr = hc.match(h2); itr;) {
        const auto i = itr.next();
        const auto p = &(*this)[i + hi];
        if (p->key == key) {
          return p;
        }
      }
    }
    return nullptr;
  }

  auto replace_or_insert(usize hash, T&& val) -> bool {
    const auto h1 = hash & _msk;
    const auto h2 = u8(hash >> 57);
    const auto hc = Ctrl::load(_buf._ptr + h1);

    if (auto itr = hc.match_val(h2)) {
      const auto i = itr.next();
      const auto p = &(*this)[h1 + i];

      // case: replace
      if (p->key == val.key) {
        mem::replace(*p, static_cast<T&&>(val));
        return true;
      }
    }

    // case: insert
    if (auto itr = hc.match(Ctrl::NIL)) {
      const auto i = itr.next();
      const auto j = (i - Ctrl::LEN) & _msk + Ctrl::LEN;
      _buf._ptr[h1 + i] = h2;
      _buf._ptr[h1 + j] = h2;
      ptr::xnew(&(*this)[h1 + i], static_cast<T&&>(val));
      this->_len += 1;
      return false;
    }

    // reserve -> insert2
    this->reserve(this->capacity());
    return this->replace_or_insert(hash, static_cast<T&&>(val));
  }

  void append(Table& other) {
    if (other.len() == 0) {
      return;
    }

    const auto p = &other[0];
    for (usize i = 0u; i < other._len; ++i) {
      if (other._buf[i] == Ctrl::NIL) {
        continue;
      }
      this->insert(p[i]);
    }

    other._len = 0;
    other._mask = 0;
  }

  void reserve(usize additional) {
    if (_len + additional < this->capacity()) {
      return;
    }
    auto tmp = mem::replace(*this, Table::with_capacity(_len + additional));
    this->append(tmp);
  }
};

}  // namespace sfc::collections::hash
